1. Field of the Invention
This invention relates to programmable architectures, and more particularly to a method and structure for a fast programmable carry chain in programmable architectures, the beginning and end of which are user-programmable.
2. Description of the Prior Art
FIG. 2 depicts a conventional n-bit adder. The adder includes n-bit carry logic elements CL.sub.0 -CL.sub.n-1 and n-bit sum logic elements (exclusive OR gates) SL.sub.0 -SL.sub.n-1. Each carry logic element CL.sub.K (K=1, 2 . . . N-1) receives two addend bits a.sub.K, b.sub.K and a carry bit C.sub.K produced by a carry logic element of a less significant bit and generates a carry C.sub.K+1 signal to a carry logic element of a more significant bit, as shown in FIG. 1(a). FIG. 1(b) is a logic presentation for a bit carry logic element as in FIG. 2 which consists of three AND gates GA1-GA3 and an OR gate GO. A sum operation for each bit can be executed by a 3-input exclusive OR (XOR) gate SL.sub.0, SL.sub.1, SL.sub.n-1 as shown in FIG. 2. In such an adder circuit, carry bits are propagated by rippling bit by bit from the least significant to the most significant bit and hence the propagation delay T.sub.PD of the adder is approximately: EQU T.sub.PD =(N-1) t.sub.c +t.sub.XOR ( 1)
where t.sub.C is the propagation delay of a single carry bit, N is the total number of bits, and t.sub.XOR is the propagation delay of the 3-input XOR gate SL.sub.0, SL.sub.1, SL.sub.n-1 used for summing in each stage.
FIG. 3 shows a conventional, programmable n-bit adder circuit which is the same as the adder circuit shown in FIG. 2, except for the AND gates G.sub.0 -G.sub.n-1. The beginning and end of a K-bit adder sequence (K.gtoreq.N) can be programmed by enabling K consecutive carry propagation in the n-bit chain through configuration bits CB.sub.0 -CB.sub.N-1 which may come from a conventional configuration control register using, for example, fuses, anti-fuses, EPROMs, EEPROMs or other programmable memory elements. The propagation delay of this programmable adder circuit is also expressed by expression (1), provided the delay of gates G.sub.0 -G.sub.N-1 is included in the propagation delay of a single carry bit or a single stage of the carry chain. In present semiconductor fabrication technologies, t.sub.C and t.sub.XOR are on the order of 1 ns/bit, hence a 24 bit add requires about 24 ns.
High-speed binary adders are important functions in many integrated circuit logic applications, including many applications designed using programmable logic. The propagation speed of the arithmetic carry path is the key to high-speed operation. There are several standard carry-lookahead schemes such as carry selection and conditional sum, which can be used in a conventional adder as shown in FIG. 2 to reduce the carry propagation delay. For example, one of such known techniques, carry-select addition is described in Joseph J. F. Cavanagh, "Digital Computer Arithmetic Design and Implementation," McGraw-Hill Book Company, 1984, pp. 117-122, incorporated here by reference. The carry select adder requires two identical parallel adders that are partitioned into certain-bit groups with a group carry being produced. Two sums are generated simultaneously, one sum assumes that the carry-in to the group is 0, the other sum assumes that the carry-in to the group is 1. Subsequently, the actual group carry is used to select the correct sum from the two sums. However, such standard "carry-lookahead" speedup schemes cannot be used in a straightforward manner to speed up the carry delay in a programmable architecture which has a programmable carry chain for producing either a sum or the most significant carry bit from two addends, and in which the beginning and end of the carry path are not known during the chip design and are user specified. So far, no prior art discloses carry-lookahead structures which are built into the chip architecture and compatible with the programmability of the carry path. Therefore, there is a need to incorporate the carry-lookahead technology into such programmable logic circuits, for example, an adder chain within a PLD, to speed up the carry delay. The difficulty is finding a carry-lookahead circuit that is compatible with the programmability of the carry path.